[Music]
my name is Chris dark and I'm a program
at robot entertainment I've been in the
industry now for around 13 years at
several different companies most
recently robot entertainment for the
last eight years I really worked on the
Orcs Must Die franchise so for those of
you not familiar familiar with orcs
here's a quick rundown you have one warm
agent friends versus hordes of orcs AI
trolls ogres and worse and weapons and
traps to hold them back from an in your
IFFT there are tons of AI don't want to
shoot you stab you and or blow you up
I'm going to be talking today about is
doing range day eyes and this franchise
specifically is that fire projectiles
I'll be talking about math code and
design all three the design drives your
math and your code keeping it fun is
your former job so most action games
have ranged AI like I mentioned I'm
going to be talking about the ones that
do projectiles some of this but not
motovan is relevant to hits can the
projectiles need to be slow enough for
the player to dodge this way the player
has a chance to have some counter play
against the eyes and it makes you a is
more fun to play against however this
means that by the time the put the
projectile gets there the player won't
be there if you're not aiming ahead this
is what you're going to get looks pretty
bad doesn't it you really want something
more like this so the first class of
projectiles we'll be talking about our
linear projectiles and then the second
or ballistic projectiles I'm going to be
talking through how to aim debug and
most importantly miss with bow types of
projectiles and a few things I ran
across while has implemented them so
let's start off by talking about
predicting player movement so first a
few assumptions we're going to make
we're typically working over a short
enough timeframe that we don't need to
worry about rotations and we also want
to make sure we ignore the player's
vertical velocity when they're jumping
otherwise it's going to throw off our
aiming results we're gonna be pretending
that we're operating in a vacuum it
helps keep the math and ultimately the
code quite a bit simpler so we need to
know which way the player is going to be
going the easiest thing to do is look at
how fast the
going right now and in what direction
and just use that this works well as
long as the players doing something like
this however when your player starts
doing things more like this it doesn't
work quite as well is there something we
can do better than just the
instantaneous velocity there is we can
use a history buffer which will give us
a more accurate result you're gonna want
to take that history buffer and tweak it
until you're accurate but players still
have a chance to dodge the projectiles
so now that we've got a velocity let's
walk through how to use that to predict
to the players future position so the
start with or mage here in a position in
our first few games just as a side note
the origin of the player is on the
ground you want to make sure you're
actually using the center of their
bounding box and not shooting at the
ground we know from our history buffer
that they're moving at some velocity and
then they're going to be moving 40
seconds we don't know how long T is yet
but we'll come back to that here in a
little bit so when you put that all
together that will give us our final
predict position X prime which is the
aboard ranges original position plus his
velocity times the amount of time he's
been traveling we'll see this again here
in just a minute first though let's talk
about linear projectiles a little bit
this is a linear projectile there's no
gravity on it it's going to go into
straight line forever or until it hits
something but before we go ahead and
fire one of these off there's a few
things we want to do we want to predict
the player's position which we'll talk
about how we're going to do then we want
to make sure that we're not going to be
firing this through a wall we may also
want to check against friendly units
between us and that predicted player
position we wound up not however we did
have the friendlies block shots because
players were a little bit baffled where
the shots were coming from since our
range units tended to be in the back we
didn't do a line of sight check though
just because we have a lot of works and
it would have been pretty performance
heavy to do so and then the other thing
you want to think about is when you're
actually going to do the math to do the
intersection prediction you can do it
before you fire off or you can do it at
the actual launch point in your
animation so now that we've got that out
of the way let's talk about how we're
looking at the projectile so like the
word range it's going to start in a
fixed position in this case it's going
to be the end of the works
crossbow it's gonna be moving at some
fixed speed we let design to said what
the speed was we also had a maximum
speed or a maximum range sorry on our
projectiles so that they would time out
after a certain amount of time and we
wouldn't have a lot of Indies cluttering
up the world and then there's gonna be
it's going to be moving for some amount
of time T since launch and since the AI
can actually fire in any direction SP
your speed times the amount of time it
spit out is actually going to form a
circle around the eye that's expanding
over time so the radius of that circle
like I said is a speed times the time
that's been out x prime which is going
to be our new projectile position live
somewhere on that expanding circle this
can also be written as the equation for
a circle which I've done here I'm gonna
be doing and showing all my math on my
slides here in 2d I for some reason I'm
not a very good artist when it comes to
3d so just just say you know this math
actually does all work in 3d without any
modification so when you take the
players move in and the projectiles move
in and you put them together you can see
what we wind up with is a circle versus
line intersection and so if we think
about a circle versus line intersection
we really have three cases we don't hit
it all we have one potential hit or we
have two potential hits so just keep
that in mind as we go here so here are
equations again for both the player
movement at the projectile movement
so you'll notice both of these have an X
Prime this is actually going to be our
intersection point where the projectile
hits the player and you also notice we
have a teen both of these for how long
it's been so we don't know T which is
our intersection time so if you take
these two equations and you solve them
30 you wind up with a quadratic equation
which you can solve using the quadratic
formula a B and C here are all scalars
there's a vet bunch of vector multiplies
in there that are just dot products for
folks interested in how we got from the
last side to this slide the online
versions these slides which will be up
shortly after GDC will actually have
that whole derivation in the appendix so
let's take our credit formula that we
got from there it's pretty simple it's
not too difficult to code this up and go
however there's a couple edge cases you
want to make sure you think about while
you're working through solving this so
first if you
take a look at the bottom of this your
intuition would be if a is zero you
don't have a valid solution but remember
we're actually solving a polynomial a T
squared plus BT plus C equals zero so we
actually do have a valid solution if a
is zero same we want to do is when we
want to take a look at the discriminant
inside of the square root here if it's
zero we wind up with one solution if
it's negative we don't have any solution
at all otherwise we're going to get two
solutions we want to take the smallest
positive solution of the two because you
want to hit as soon as you can if you
have a negative solution its invalid in
my experience you're almost always going
to wind up with one invalid solution
it's very rare to actually wind up with
two valid solutions out of this so once
you have your solution for time T you
can circle back around and plug that
into the warm Age movement equation and
this will give us x prime the location
we're aiming at you can take X prime and
your initial firing point from the orc
and that will give you the direction
you're firing in and then if you
multiply that by the speed the
projectile is firing at you will have
your final projectile velocity as you
can see here so what happens if you
don't come up with a valid solution
because it can and will happen to you so
if you did your math before you played
your firing animation you can just not
fire at all nobody will ever know
anything happened however if you like us
and you actually did your math at the
time you hit the firing point in your
animation the works already played a
firing animation it looks really bad in
our experience if nothing comes out of
the crossbow at that point so we wound
up doing was actually just shooting a
projectile at the players current
position nobody ever really noticed it
happened frequently enough it still
looked fine and we have a lot of cases
to where the player wasn't moving around
so it still actually looked pretty
decent so once you have your math all
coding up and in your game you may want
to actually visually double check it
just to make sure it's working like it
expected so we did that so the first
thing we did is in under the orc here we
drew the launch point you can't see it
because he's standing on top of it the
next one you do here in red was the
actual predicted point of intersection
between the warm age and the projectile
then we drew the motion of the
projectile every frame we just draw its
position in white and then we draw the
final endpoint impact point in blue so
if you notice the impact point and the
predicted point are actually slightly
different here but that's expected
since the players collision is an
important space in our case it's
actually a cylinder so that impact point
is actually on the surface of the
cylinder so those two points are close
enough that this is what we would expect
to see and this lines up so now we've
talked about hitting a little bit with
linear projectiles let's talk about
missing with them we're trying to write
funny opponents here and not aimbots so
we wound up giving to design two
different accuracy settings one for
horizontal and one for vertical we would
then take that and do a random role
between the negative value and the
positive value so we defaulted to two
degrees interestingly enough for both
horizontal and vertical which gave us a
total cone of four degrees we would then
take those two rotations generate a
rotation matrix and multiple multiply it
by our initial direction vector to
randomize the shots one thing we noted
is specially on the vertical is that you
want to avoid shooting too far up or too
far down especially for shooting to the
ground
it made the eye look especially dumb
they are orcs but at the end of the day
you won't don't want them to look too
dumb after all so this worked well we
had this in our game for quite a while
and then we added barricades which are
obstructions have blocked the eyes paths
and that they can damage and we noticed
that archers are really being rough on
the barricades as you can see here
pretty much all their shots are hitting
the barricades it looks really bad
players were complaining because all
they're expensive traps are getting torn
up so what we wound up doing is we added
a new value into the equation we called
tilt that we applied to the vertical
value only so tilt automatically shrunk
the cone by half so now we had a two
degree cone instead of a four degree
cone and then we had a range 0 to 1
where point 5 kept it centered
0 would remove the bottom and 1 would
remove the top we wound up defaulting
our tilt value to 3/4 which got the
majority the shots clear of the
barricades as you can see here we didn't
want to remove all of the down because
we do want to incent players to not
fight around their barricades but we
didn't want to be overly penalizing
either as it turns out that actually
still wasn't enough to fix all of our
problems with barricades we had a number
of short characters in the game as you
can see here whose center point which is
what we were aiming at was actually
below the barricade height so what we
did for those cases is we had the AI
look at the height of the thing they
were shooting at and if their Center was
below the top of the barricades we'd
pull it up but not above the top of the
player us collision cylinder we threw a
warning if that
point actually did need to go over the
top of the cylinder fortunately it's
never come up for us so here's
everything all working on a layered
projectile
so in summary they have a fixed constant
speed you want to take that speed and
the player movement prediction to solve
for the intersection time and location
as far as missing we used a cone we used
a different angle for both horizontal
and vertical in that cone and we did
need to do some additional game
dependent tweaks and you may as well so
next up let's talk about their cousins
the ballistic projectiles so this is a
ballistic projectile unlike a linear
projectile it has an upwards initial
velocity or some velocity to its initial
velocity and it's affected by gravity so
you get this nice arcing motion so you
really want to do the same set of
operations here as you did on the linear
projectile before firing you want to
predict the player's position one slight
difference here is you may actually want
to predict on the ground which because a
lot of times you'll have a group bouncy
grenade and this will actually get you
less bounciness and will land it closer
to the player we want to do a
line-of-sight check in theory you'd
actually want to do a piecewise
approximation of your arc to make sure
you're not going to hit anything up in
the air
however our hallways in our game were
pretty much square and didn't have any
obstructions I've talked top so we
actually just kept the straight line
check it saved us some performance and
was good enough for us
but your mileage may vary on that point
and then just like before we wanted to
look at when we were doing our math
either before the shot or at the time of
the shot so this is your basic ballistic
motion equation if you're interested in
seeing how this is all derived out I'm
gonna refer you to last year's excellent
talk on building a better jump where
it's talked through in some depth so
after seeing how we solved for a linear
projectile you'd probably assume we just
take this and the one range movement
equation and put them together and solve
them except you wind up with this which
is a quartic equation and can be a
little bit hairy to solve if you're
curious how these are actually solved
I've got some good references in the
note graphics gems 1 is probably the
best one we actually wound up doing some
reproach mate approximations here in
cheating so how did you cheat you might
wonder
well we started with an arc and we noted
that you could actually break the motion
of the arc into horizontal and vertical
pieces so we solved the horizontal one
first with actually our good old linear
projectile code which he already had the
one slight difference here is we
actually had a maximum range on this
which I'll talk about more here in a
little bit we go ahead we solve that for
t we'd get our intersection point and
we're done so we take that intersection
point with our vertical motion and say
this is where we want it to land so
let's solve for our throw so that will
in fact land at our intersection point
so we'll start with our projectile
equation from a couple slides back and
we'll break into x and y-components here
which are going to we're just going to
solve at the distance of the target so X
is going to be your horizontal distance
and Y is going to be a vertical distance
we want to solve these for theta once we
can use to calculate our launch speeds
so we have two equations and two
unknowns and if you take these and you
solve them you wind up with this which
is actually the quadratic occasion again
and once you solve that through for
theta
you're going to wind up with this and
you can use this to get your launch
angle so you may have one solution in
which case you're good you know you're
throwing the list you're done if you
wind up with no solution we just threw
it straight at the player but we kept
gravity on the projectile we found it
was important to keep gravity on there
just for the feel of things sometimes it
wouldn't land close enough but
frequently it was good enough that
nobody ever noticed and then sometimes
you wind up with two solutions in which
case we just picked this smaller of the
two we felt that looked better the
higher of the two frequently was a
pretty large arc which I'll talk about
again here in a minute
so now that we have theta we can solve
for our speeds which is a pretty simple
solve you just multiply by the cosine of
the angle or the sine of the angle and
we're driving that from just basic trig
equations sohcahtoa in this case if
anybody remembers back to high school
algebra so now that we've got these we
actually need a horizontal and vertical
vector to throw along that way it all
works when you have a case like this so
for calculating throw vectors you're
going to have R which is the vector
between the launch point and the target
and which may be non horizontal as it is
here
all you want to do is actually just
project that down to the ground the math
for that winds up being you're just
removing the up component of your vector
nice and simple then you take that
component which I'm calling our prime
multiplying it by your horizontal speed
and then adding your vertical speed in
and you are now in the grenade throwing
business so one note here is that using
the quadratic equation like we did is
not a perfect solution to this problem
you will hit where you want to but it
may alter your impact time slightly we
found that for us and for the ranges we
were fighting at it didn't matter and it
still worked just fine and the fact rod
Rene's area we didn't really hurt much
either there so just something to be
aware of if you use this solution so as
far as actually calculating what our
base throw speed was we change our
approach between games here so at first
we just had a constant speed that design
would set for how fast these were thrown
however it was kind of difficult to work
with because they wouldn't know how much
arc that would give them kind of what
the feel was on that so we found
actually giving them some values to play
with it more just described how the
bridgetta was gonna behave give us
better looking results so instead of one
value we actually gave them three so we
gave them a gravity multiplier so a
larger gravity multiplier would make the
projectile heavier and feel a little bit
weightier like a grenade making it
smaller would give you more of an arc we
gave them an ideal launch angle which we
defaulted to 45 degrees that way you get
since a 45 degree launch of the
projectile will give you the maximum
range for speed would actually give us
the lowest possible speed there
I don't think design ever actually
changes from 45 degrees but the option
was there if they wanted it and then
like I mentioned earlier we had a
maximum range we had a little bit of a
constraint on how far that could be
which I'll talk about here again in a
minute
so solving out for our throat for a
drive through a speed from that works
just like before we're splitting into x
and y components like we did and then
we're actually gonna solve these for
where the projectile comes back to the
ground at the maximum range and this
will wind up being the speed we used
earlier just a friendly reminder all the
derivations for all of these are gonna
be on the online slides later if you're
curious how the math actually all works
kind of beneath the covers and then
we're actually also going to use those
trig identities again to calculate our
horizontal through a speed specifically
so maximum range which I've mentioned a
couple of times so our designing our
game agreed on a minimum ceiling height
which is to say nothing will ever be
lower than this don't forget to take
into account when you're actually
calculating how high that is that you
want to calculate it from the throw
point of the character not from the
ground so different characters might
actually have a different height here so
we would take that height we would plug
it in the projectile equation and we'd
solve it through and wind up with our
possible maximum range for that height
debugging this is actually pretty
similar to debugging linear prevent
projectiles we had the same colors did
the same things one thing you might
notice here though is we actually had a
couple of impact points since their
grenades will bounce around that's okay
and that's expected so one problem we
ran across with these grenades is when
the players got really close so you got
something like this which and it's not
really so good you really wouldn't want
to ship with this right so we wound up
cheating a little bit to solve this we
noticed it was really only when the
player got close so we had a maximum
angle of 70 degrees we used in our game
and then we had a minimum distance that
we set to about two to three meters and
that actually seemed to work pretty well
for us the players get close the eyes
were just do a straight line throw again
with gravity and it looked good later on
in the game we actually wanted making an
AI change so when players got close
enough the eyes would just break off
doing range attacks it wound up making
this a little bit better and it also end
up looking better because an Oryx
shooting you with a crossbow when he's
right up in your face like this it it
just looks a little bit silly it also
gave players one other way to counter
play against range AI since they could
get up close to them and for ci to break
off and continue running down the path
there are some other ways you can
possibly cheat physics here I've got
some more information on these and the
references if you're curious all of them
have different trade-offs so ours is not
the only way to solve it but we were we
were happy of the results so as far as
ballistic projectiles go you still want
to be able to miss so the first project
we did these we actually just picked a
random point in a circle around the
player and just or the predicted
position of the player sorry and then we
threw in there worked fine we shipped
with it
not a problem we actually went up
changing a little bit on our latest game
the thing we noticed was players were
not always facing towards the grenade
throwing units
and so they would frequently miss the
fact that a grenade and just shown up
and then they'd be like hey where did
that damage come from that's not cool
so what we went up doing was a handful
of things so we added a few sound of the
grenade there was a nice hissing sound
as it flew through the air is 3d so as
you'd hear getting closer closer closer
closer then we beefed up the impact
sounds so there's a nice solid clunk
when I hate you or hit the ground nearby
and then as you can see here we also
hadn't a decal to show the danger zone
to give the player notice it was there
and give him a chance to run out of the
way as a result we actually pulled off
the missing in a circle code and just
had the grenade throwing units always
hit the player we actually were a lot
happy the results of this and we were
just trying to throw in a circle around
the player so when you put it all
together this is what you get for
ballistic projectiles so we had a
derived speed on these we threw them
with an arc we came up with our
approximate solution that we were happy
with and then we solved it with a
quadratic equation you may need to if
you use that solution you may need to
compensate for high arcs or some other
edge cases as far as missing goes you
can either aim around the player or just
make the grenades avoidable so wrapping
up make sure you aim ahead of the player
make sure it's fun fun is your priority
here it's okay to cheat as long as it's
fun and looks good at the end of the day
make sure players have a chance to react
AIS we're trying to write a fun opponent
and not an aimbot and then make sure
design can control your course ID with
parameters and then derive your math
code and fun from there any questions if
you have questions by the way please
step up to the mic
you